Several significant models have been developed that enable the study ofdiffusion of signals across biological, social and engineered networks. Withinthese established frameworks, the inverse problem of identifying the source ofthe propagated signal is challenging, owing to the numerous alternativepossibilities for signal progression through the network. In real worldnetworks, the challenge of determining sources is compounded as the truepropagation dynamics are typically unknown, and when they have been directlymeasured, they rarely conform to the assumptions of any of the well-studiedmodels. In this paper we introduce a method called Network Infusion (NI) thathas been designed to circumvent these issues, making source inference practicalfor large, complex real world networks. The key idea is that to infer thesource node in the network, full characterization of diffusion dynamics, inmany cases, may not be necessary. This objective is achieved by creating adiffusion kernel that well-approximates standard diffusion models, but lendsitself to inversion, by design, via likelihood maximization or errorminimization. We apply NI for both single-source and multi-source diffusion,for both single-snapshot and multi-snapshot observations, and for bothhomogeneous and heterogeneous diffusion setups. We prove the mean-fieldoptimality of NI for different scenarios, and demonstrate its effectivenessover several synthetic networks. Moreover, we apply NI to a real-dataapplication, identifying news sources in the Digg social network, anddemonstrate the effectiveness of NI compared to existing methods. Finally, wepropose an integrative source inference framework that combines NI with adistance centrality-based method, which leads to a robust performance in caseswhere the underlying dynamics are unknown.
展开▼
